"""
Problem 47: https://projecteuler.net/problem=47

Combinatoric selections

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each.
What is the first of these numbers?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/14
'''


N = 1000000
Primes = [True]*N
Primes[0] = False
Primes[1] = False
for i in range(2, N):
    for k in range(i, (N-1)//i+1):
        Primes[i*k] = False


def factors(n: int):
    '''
    >>> print(factors(644))
    3
    >>> print(factors(645))
    3
    >>> print(factors(646))
    3
    '''
    if n < 2 or Primes[n]:
        return 0
    else:
        nums = set()
        while n != 1:
            for x in range(2, n+1):
                if Primes[x] and n % x == 0:
                    nums.add(x)
                    # print(n,x)
                    n = n//x
                    break
        return len(nums)


def factorsD(n: int, d: int = 4) -> bool:
    '''
    >>> assert factorsD(3*2*5*13,4)
    >>> assert factorsD(3*2*5,3)
    >>> assert factorsD(3*2*5*13*19,5)
    '''
    if Primes[n]:
        return d == 0
    else:
        nums = set()
        while n != 1:
            for x in range(2, n+1):
                if Primes[x] and n % x == 0:
                    n = n//x
                    nums.add(x)
                    if len(nums) > d:
                        return False

                    break

        if len(nums) < d:
            return False
        else:
            return True


def solution() -> int:
    '''
    n, n+1, n+2, n+3, are not primes
    '''
    n = 2
    while True:
        # print(n)
        if not factorsD(n, 4):
            n += 1
            continue
        if not factorsD(n+1, 4):
            n += 2
            continue
        if not factorsD(n+2, 4):
            n += 3
            continue
        if not factorsD(n+3, 4):
            n += 4
            continue
        return n


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 134043
